package top.ivansong92.example.leetcode.learning.data.struct.tree;


import java.util.*;
import java.util.stream.Collectors;

public class TestExampleV3 {
    /**
     * Definition for a binary tree node.
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    /**
     * 437. 路径总和 III
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int num = 0;
        if (root.val == targetSum) {
            num ++;
        }
        num += getAnyPathMatch(root.left, root.val, targetSum) + getAnyPathMatch(root.right, root.val, targetSum);
        return num + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int getAnyPathMatch(TreeNode node, int parentVal, int targetSum) {
        if (node == null) {
            return 0;
        }

        int val = node.val + parentVal;
        int num = 0;
        if (val == targetSum) {
            num++;
        }

        num += getAnyPathMatch(node.left, val, targetSum);
        num += getAnyPathMatch(node.right, val, targetSum);

        return num;
    }


    /**
     * 235. 二叉搜索树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        int valP = p.val, val = root.val, valQ = q.val;

        if (valP > val && valQ > val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        if (valP < val && valQ < val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        int plus = key - root.val;
        if (plus > 0) {
            root.right = deleteNode(root.right, key);
            return root;
        } else if (plus < 0) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if (root.left == null) {
            TreeNode node = root.right;
            root.right = null;
            return node;
        } else if (root.right == null) {
            TreeNode node = root.left;
            root.left = null;
            return node;
        } else {
            TreeNode newNode = getMinLeft(root.right);
            newNode.right = moveNode(root.right);
            newNode.left = root.left;
            root.right = null;
            root.left = null;
            return newNode;
        }
    }

    private TreeNode getMinLeft(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return getMinLeft(node.left);
    }

    private TreeNode moveNode(TreeNode node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = moveNode(node.left);
        return node;
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }

        if (k == 1 && root.left == null) {
            return root.val;
        }

        List<Integer> list = new LinkedList<>();

        halfInOrderSearch(root, list, k);

        return list.get(k - 1);

    }

    private void halfInOrderSearch(TreeNode node, List<Integer> list, int limit) {
        if (node == null) {
            return;
        }
        halfInOrderSearch(node.left, list, limit);
        if (list.size() == limit) {
            return;
        }

        list.add(node.val);
        if (list.size() == limit) {
            return;
        }

        halfInOrderSearch(node.right, list, limit);
    }


    /**
     * 236. 二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestorV2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        boolean pLeft = matchNodes(root.left, p.val);
        boolean qLeft = matchNodes(root.left, q.val);
        if (pLeft ^ qLeft) {
            return root;
        }

        if (pLeft) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }

    public boolean matchNodes(TreeNode node, int val) {
        if (node == null) {
            return false;
        }

        if (node.val == val) {
            return true;
        }

        return matchNodes(node.left, val) || matchNodes(node.right, val);
    }



    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }


    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val;
        }

        return doRobTree(root)[2];
    }


    private int[] doRobTree(TreeNode node) {
        if (node == null) {
            return new int[3];
        }
        int[] left = doRobTree(node.left);
        int[] right = doRobTree(node.right);
        int[] res = new int[3];
        res[0] = left[2] + right[2];
        res[1] = left[0] + right[0] + node.val;
        res[2] = Math.max(res[0], res[1]);
        return res;
    }

    /**
     * 剑指 Offer 26. 树的子结构
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return true;
        } else if (A == null || B == null) {
            return false;
        }

        return doSubMatch(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean doSubMatch(TreeNode node, TreeNode sub) {
        if (sub == null) {
            return true;
        }
        if (node == null) {
            return false;
        }
        return node.val == sub.val && doSubMatch(node.left, sub.left) && doSubMatch(node.right, sub.right);
    }

    /**
     * 剑指 Offer 07. 重建二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        int len = preorder.length;
        if (len == 1) {
            return new TreeNode(preorder[0]);
        }
        return doBuildTree(preorder, inorder);
    }

    private TreeNode doBuildTree(int[] preOrder, int[] inOrder) {
        if (preOrder == null) {
            return null;
        }
        int len = preOrder.length;
        int val = preOrder[0];
        TreeNode node = new TreeNode(val);
        if (len == 1) {
            return node;
        }

        int index = 0;
        for(int i = 0; i < len; i ++) {
            if (inOrder[i] == val) {
                index = i;
                break;
            }
        }

        if (index > 0) {
            node.left = doBuildTree(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(inOrder,0, index));
        }

        if (index < len - 1) {
            node.right = doBuildTree(Arrays.copyOfRange(preOrder, index + 1 , len), Arrays.copyOfRange(inOrder,index + 1, len));
        }

        return node;
    }

    public TreeNode buildTreeV2(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        int len = preorder.length;
        if (len == 1) {
            return new TreeNode(preorder[0]);
        }
        return doBuildTree(preorder, inorder);
    }


}
